package com.klangner.go.ab;

import java.util.Collection;
import java.util.Iterator;

import com.klangner.go.model.GameStatus;
import com.klangner.go.model.IGameState;
import com.klangner.go.model.Move;



/**
 * This class models the Alpha-Beta Pruning algorithm for game trees: it's
 * an improvement over the classical Min-Max algorithm
 * The idea is to avoid exploration of clearly hopeless branches
 * The result is the same as with Min-Max, but faster (especially
 * when we have a good ordering of the to-be-explored nodes).
 */
public class AlphaBetaPruning {

	/** Max alpha beta value */
	private static float MAX_VALUE = 1;
	/** Min alpha beta value */
	private static float MIN_VALUE = -1;
	
  /** stimator used to estimate the value of a given position */
  private IEstimator estimator;

  /** Move selector */
  private IMoveSelector moveSelector;
  
  /** Tree max depth */
  private int maxDepth = 1;
  
  //----------------------------------------------------------------------------
  public AlphaBetaPruning( int maxDepth, IEstimator estimator, IMoveSelector moveSelector ){
  	
    this.maxDepth = maxDepth;
    this.estimator = estimator;
    this.moveSelector = moveSelector;
  }

	//----------------------------------------------------------------------------
  /**
   * Select best move
   */
	public Move getBestMove(IGameState gameState) {

	  EstimatedMove estimatedMove = expandAlphaBeta( gameState,
	                                                 maxDepth,
	                                                 MIN_VALUE, MAX_VALUE );
	
	  return estimatedMove.move;
	}


  //----------------------------------------------------------------------------
  private EstimatedMove expandAlphaBeta(IGameState gameState, int maxDepth, 
  		float alpha, float beta ) 
  {

  	int turn = gameState.getTurnColor();
  	
	  EstimatedMove bestSoFar = new EstimatedMove(new Move(-1, -1, turn), alpha);

    if( maxDepth == 0 || gameState.getStatus() != GameStatus.IN_PROGRESS) {
                
    	// No more branching
      bestSoFar.alpha = estimator.estimatePosition( gameState, turn );
      return bestSoFar;
    }


		Collection<Move> candidates = moveSelector.getCandidates(gameState.getBoard(), turn);
		
		if ( candidates.isEmpty() ) {
		
	    float estimated = estimator.estimatePosition( gameState, turn );
	    bestSoFar.alpha = estimated;
		}
		else {

	   	Iterator<Move> it = candidates.iterator();
	
	   	while ( it.hasNext() ) {
	   		Move move = it.next();
	
	      IGameState nextPosition = gameState.makeCopy();
	      nextPosition.makeMove( move );
	
	      float value = -(expandAlphaBeta(nextPosition, maxDepth-1,
	                          -beta, -bestSoFar.alpha).alpha);
	
	      if (bestSoFar.alpha < value){
	
	          bestSoFar.alpha = value;
	          bestSoFar.move = move;
	      }
	
	      if ( bestSoFar.alpha >= beta ){
	          return bestSoFar;
	      }
	    }
	    
	  }

    return bestSoFar;
  }


  //----------------------------------------------------------------------------
  // Private members
  static class EstimatedMove {
      
  	public EstimatedMove( Move move, float value ){
	    this.move = move;
	    this.alpha = value;
    }

    public String toString() {
        return "(" + move.toString() + " : " + alpha + ")";
    }

    Move move;
    private float alpha;
  };

}
